﻿// 5973. 最佳路径.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

/*
https://www.acwing.com/problem/content/5976/

给定一个 n
 行 m
 列的方格棋盘。

你需要操纵一枚棋子从最下方一行的任意一个方格出发，移动至最上方一行的任意一个方格结束。

棋子的移动规则为每次移动可以向左上方或右上方斜走一格，不得往回走，也不得走出棋盘。

QQ截图20240924175550.png

每一个方格都有一个 0∼9
 的积分，当棋子进入一个方格后（包括起点方格和终点方格）就可以获得该方格的全部积分。

我们希望：

获得的总积分必须能被 k+1
 整除。
在满足上一要求的前提下，获得的总积分尽可能多。
请你给出一种最佳路径方案。

输入格式
第一行包含三个整数 n,m,k
。

接下来 n
 行，每行包含 m
 个 0∼9
 的整数（整数之间没有空格），用来表示棋盘内每个方格的积分，其中第一行对应棋盘最上行，最后一行对应棋盘最下行。

输出格式
如果不存在满足全部条件的可行方案，则输出 -1 即可。

否则，你需要输出三行答案：

第一行输出一个整数，表示可以获得的最大总积分。注意，总积分必须能够被 k+1
 整除。
第二行输出一个整数，表示你的起点方格所在的列数，棋盘的列从左到右依次编号为 1∼m
。
第三行输出一个长度为 n−1
 的由 L 和 R 组成的字符串，其中第 i
 个字符表示棋子的第 i
 次移动的前进方向，L 表示左上方向，R 表示右上方向。
如果方案不唯一，输出任意合理方案均可。

数据范围
前 5
 个测试点满足 2≤n,m≤4
。
所有测试点满足 2≤n,m≤100
，0≤k≤10
。

输入样例1：
3 3 1
123
456
789
输出样例1：
16
2
RL
输入样例2:
3 3 0
123
456
789
输出样例2：
17
3
LR
输入样例3：
2 2 10
98
75
输出样例3：
-1
*/
#include <iostream>

int main()
{
    std::cout << "Hello World!\n";
}
 